package utils;

import java.util.ArrayList;

public class TreeUtils {

	public static ArrayList<Node> temporary = new ArrayList<Node>();

	/**
	 * Search a node in a tree INVALID
	 * 
	 * @param tree
	 * @param node
	 * @return a node
	 */
	public static Node search(Node tree, Node node) {
		if (tree.ID == node.ID)
			return tree;
		else
			for (Node child : tree.children)
				return search(child, node);
		return null;
	}

	/**
	 * Search a node in a tree by id INVALID
	 * 
	 * @param tree
	 * @param id
	 * @return a node
	 */
	public static Node searchById(Node tree, int id) {
		if (tree.ID == id)
			return tree;

		Node n = null;
		for (Node child : tree.children) {
			n = searchById(child, id);
			if (n != null)
				return n;
		}
		return n;
	}

	/**
	 * Search a node in a tree by label
	 * 
	 * @param tree
	 * @param label
	 * @param list
	 * @return a list of nodes
	 */
	public static ArrayList<Node> searchByLabel(Node tree, String label) {
		temporary.clear();
		temporary = searchByLabel(tree, label, temporary);
		return temporary;
	}

	private static ArrayList<Node> searchByLabel(Node tree, String label,
			ArrayList<Node> list) {
		if (tree.label.equals(label))
			list.add(tree);

		for (Node child : tree.children)
			list = searchByLabel(child, label, list);

		return list;
	}

	/**
	 * get all leaves for a given tree
	 * 
	 * @param tree
	 * @return
	 */
	public static ArrayList<Node> getLeaves(Node tree) {
		ArrayList<Node> list = new ArrayList<Node>();
		getLeaves(tree, list);
		return list;
	}

	/**
	 * This is used as internal function in order to build recursively the
	 * leaves list
	 * 
	 * @param tree
	 * @param list
	 * @return
	 */
	private static void getLeaves(Node tree, ArrayList<Node> list) {
		if (tree.children.size() == 0)
			list.add(tree);

		for (Node child : tree.children)
			getLeaves(child, list);
	}

	/**
	 * get all nodes which are not leaves for a given tree
	 * 
	 * @param tree
	 * @return
	 */
	public static ArrayList<Node> getIntermediateNodes(Node tree) {
		ArrayList<Node> list = new ArrayList<Node>();
		getIntermediateNodes(tree, list);
		return list;
	}

	/**
	 * This is used as internal function in order to build recursively the
	 * non-leaves list
	 * 
	 * @param tree
	 * @param list
	 * @return
	 */
	private static void getIntermediateNodes(Node tree, ArrayList<Node> list) {
		if (tree.children.size() != 0)
			list.add(tree);
		for (Node child : tree.children)
			getIntermediateNodes(child, list);
	}

	/**
	 * For each node in nodes find all possible paths in tree
	 * 
	 * @param tree
	 * @param nodes
	 * @return all possible paths from configuration for a given (rule)tree
	 */
	public static ArrayList<Path> getPaths(Node tree, ArrayList<Node> nodes) {
		Node[] nds = new Node[nodes.size()];
		ArrayList<Path> paths = new ArrayList<Path>();

		int i = 0;
		for (Node n : nodes) {
			if (n.parent != null) {
				nds[i] = n;
				i++;
			}
		}

		int size = i;
		for (i = 0; i < size; i++) {
			ArrayList<Node> feasibleNodes = searchByLabel(tree, nds[i].label);
			for (Node f : feasibleNodes) {
				Node parent = f.parent;
				while (parent.ID != tree.ID) {
					if (parent.label.equals(nds[i].parent.label)) {
						paths.add(new Path(parent, f, nds[i]));
					}
					parent = parent.parent;
				}
			}
		}

		return paths;
	}

	/**
	 * Prints a tree like an XML
	 * 
	 * @param tree
	 * @param indent
	 */
	public static void printTree(Node tree, String indent) {
		if (tree == null)
			return;

		if (tree.children.size() == 0)
			System.out.print(indent + "<" + tree.label + ">");
		else
			System.out.println(indent + "<" + tree.label + ">");

		for (Node ch : tree.children) {
			printTree(ch, indent + "  ");
		}

		if (tree.children.size() == 0)
			System.out.println("</" + tree.label + ">");
		else
			System.out.println(indent + "</" + tree.label + ">");
	}

	/**
	 * Finds the context for each path in leavesPaths using intermediatePaths
	 * 
	 * @param leavesPaths
	 * @param intermediatePaths
	 * @param ruleRootLabel
	 * @return The list of contexts for each path
	 */
	public static ArrayList<Path> getPathContext(ArrayList<Path> leavesPaths,
			ArrayList<Path> intermediatePaths, String ruleRootLabel) {

		ArrayList<Path> closure = new ArrayList<Path>();
		Path[] ipaths = new Path[intermediatePaths.size()];

		int i = 0;
		for (Path p : intermediatePaths) {
			ipaths[i] = p;
			i++;
		}

		i = 0;
		while (i < leavesPaths.size()) {
			Path cpath = leavesPaths.get(i);
			for (int j = 0; j < ipaths.length; j++) {
				if (cpath.root.ID == ipaths[j].leaf.ID) {
					leavesPaths.add(new Path(ipaths[j].root, cpath.leaf,
							cpath.corespondingNode));
				}
			}
			i++;
		}

		for (Path p : leavesPaths) {
			if (p.root.label == ruleRootLabel) {
				closure.add(p);
			}
		}

		return closure;
	}

	/**
	 * This is called only for the case when a rule
	 * has a single node. If there are more than one node(label)
	 * in the configuration which have the same label as the rule node
	 * then add some ambiguous paths.
	 * @param list
	 * @return
	 */
	public static ArrayList<AmbigousPath> detectAmbiguityForList(ArrayList<Node> list, Node config) {
		ArrayList<AmbigousPath> ambiguous = new ArrayList<AmbigousPath>();
		Node[] nodes = new Node[list.size()];
		
		// collect nodes
		int i = 0;
		for (Node p : list) {
			nodes[i] = p;
			i++;
		}

		// report all ambiguities
		for(i = 0; i < nodes.length - 1; i++)
			for(int j = 0; j < nodes.length; j++)
			{
				ambiguous.add(new AmbigousPath(new Path(config, nodes[i], null), new Path(config, nodes[j], null), nodes[i].label));
			}
		
		return ambiguous;
	}
	
	/**
	 * Compares each pair of path contexts to check ambiguity
	 * 
	 * @param pathContexts
	 * @return a list of AmbigousPath if there are ambiguities and null
	 *         otherwise
	 */
	public static ArrayList<AmbigousPath> detectAmbiguity(
			ArrayList<Path> pathContexts) {
		Path[] paths = new Path[pathContexts.size()];
		ArrayList<AmbigousPath> ambiguous = new ArrayList<AmbigousPath>();

		// collect paths
		int i = 0;
		for (Path p : pathContexts) {
			paths[i] = p;
			i++;
		}

		for (i = 0; i < paths.length - 1; i++)
			for (int j = i + 1; j < paths.length; j++) {
				if (paths[i].leaf.label == paths[j].leaf.label) {
					// two paths with the same leaf label
					if (paths[i].corespondingNode.parent.label == paths[j].corespondingNode.parent.label) {
						// ... and the same label for their (leafs) parents in
						// rule tree
						Node parent1 = paths[i].leaf.parent;
						Node parent2 = paths[j].leaf.parent;
						boolean found = false;
						String clabel = paths[i].corespondingNode.parent.label;

						while (!found) {
							// stop if parent1 reached the root
							if (parent1 == null)
								break;
							// stop if parent2 reached the root
							if (parent2 == null)
								break;
							// handle the common parent
							if (parent1.ID == parent2.ID) {
								// TODO Analyze multiplicity
								
								ambiguous.add(new AmbigousPath(paths[i],
										paths[j], paths[i].leaf.label));
								found = true;
							} else
								// these are two ambiguous paths because
								// parents reached the roots which have the same label
								if (parent1.label == paths[i].root.label
									&& parent2.label == paths[j].root.label) {
								ambiguous.add(new AmbigousPath(paths[i],
										paths[j], paths[i].leaf.label));
								found = true;
							}
							
							// go up if the labels for parents equal
							// with clabel => this avoids the infinite loop
							if (parent1.label == parent2.label
									&& parent1.label == clabel) {
								parent1 = parent1.parent;
								parent2 = parent2.parent;
							}
							
							// go up with parent1 if clabel not reached
							if (parent1.label != clabel)
								parent1 = parent1.parent;
							
							// go up with parent2 if clabel not reached
							if (parent2.label != clabel)
								parent2 = parent2.parent;
						}

					}
				}
			}

		return ambiguous.size() == 0 ? null : ambiguous;
	}

	/**
	 * Merges a list of paths into a tree This method works only for paths and
	 * it doesn't work for merging trees.
	 * 
	 * @param paths
	 * @return Node
	 */
	public static Node merge(ArrayList<Path> paths) {
		Node root = null;
		Path[] branches = new Path[paths.size()];

		// store all paths into an array
		int i = 0;
		for (Path p : paths) {
			// get only paths, not the whole tree
			branches[i] = p.getPath();
			i++;
		}

		// add each branch to a tree
		for (i = 0; i < branches.length; i++) {
			if (root == null)
				root = (Node) branches[i].root;
			else {
				Node brit = branches[i].leaf;
				Node node = null;
				while (node == null) {
					brit = brit.parent;
					node = TreeUtils.searchById(root, brit.ID);
				}

				node.children.add(brit.children.get(0));
			}
		}

		return root;
	}

	
	/**
	 * Checks (recursively) if a cell name used in a rule is defined in the configuration
	 * @param rule
	 * @param configuration
	 * @return true if all cell names used in the rule are defined
	 */
	public static String validateCellNames(Node rule, Node configuration) {
		return null;
	}
	
	public static ArrayList<Node> getTreeLabels()
	{
		return null;
	}

}
